// 版权归Go作者所有。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// 此文件实现二进制搜索。

package sort

// Search使用二进制搜索在[0，n]中查找并返回f（i）为true的最小索引i 
// ，假设在[0，n]范围内，
// f（i）==true意味着f（i+1）==true。也就是说，Search要求
// f对于输入范围的某些前缀（可能为空）为false[0，n）
// 然后对余数（可能为空）返回true；搜索返回
// 第一个true索引。如果没有这样的索引，搜索返回n.
// （请注意，“未找到”返回值不是-1，例如，
// strings.index。）
// 搜索调用f（i）只有我在这个范围内[0，n）.
// 
// 搜索的一个常见用法是在
// 一个排序的、可索引的数据结构（如数组或切片）中查找值x的索引i。
// 在这种情况下，参数f（通常是闭包）捕获要搜索的值
// 以及数据结构是如何定义的例如，给定一个按升序排序的切片数据，调用搜索（len（data），func（i int）bool{return data[i]>=23}）返回最小的索引i，这样数据[i]>=23.如果调用方
// 想要查找23是否在片中，则必须测试数据[i]==23 
// 分别。
// 
// 搜索按降序排序的数据将使用<=
// 运算符而不是>=运算符。
// 
// 要完成上述示例，以下代码尝试在整数数据片中查找值
// x按升序排序：
// 
// x:=23 
// i:=sort.Search（len（数据）、func（int）bool{return data[i]>=x}）
// /如果我<len（数据）和数据[i]=x{
// /x出现在数据[i]
// /}其他{
// /x不存在于数据中，
// /但我是它将被插入的索引。
// }
// /
// 作为一个更古怪的例子，这个程序猜测你的数字：
// 
// /func猜测游戏（）{
// var s string 
// fmt.Printf（“从0到100中选择一个整数。\n”）
// answer:=sort.Search（100，func（i int）bool{
// fmt.Printf（“您的号码是不是<=%d？”，i）
// fmt.Printf（“您的号码是%d.\n”，答案）
// }
// /
func Search(n int, f func(int) bool) int {
	// /定义f（-1）=false和f（n）=true。
	// 不变量：f（i-1）=false，f（j）=true。
	i, j := 0, n
	for i < j {
		h := int(uint(i+j) >> 1) // 在计算h 
		// i时避免溢出≤ h<j 
		if !f(h) {
			i = h + 1 // 保留f（i-1）=假
		} else {
			j = h // 保留f（j）=真
		}
	}
	// i==j，f（i-1）=假，f（j）（=f（i））==true=>答案是i.
	return i
}

// 常见情况的便利包装。

// SearchInts在已排序的ints片中搜索x，并返回搜索指定的索引
// 返回值是插入x的索引，如果x是
// 不存在（可能是len（a））.
// 切片必须按升序排序。
// 
func SearchInts(a []int, x int) int {
	return Search(len(a), func(i int) bool { return a[i] >= x })
}

// SearchFloat64s在已排序的float64s切片中搜索x，并返回搜索指定的索引
// 如果x不存在，则返回值为插入x的索引（可以是len（a））.
// 切片必须按升序排序。
// 
func SearchFloat64s(a []float64, x float64) int {
	return Search(len(a), func(i int) bool { return a[i] >= x })
}

// SearchString在已排序的字符串切片中搜索x，并返回搜索指定的索引
// 如果x不存在，则返回值为插入x的索引（可以是len（a））.
// 切片必须按升序排序。
// 
func SearchStrings(a []string, x string) int {
	return Search(len(a), func(i int) bool { return a[i] >= x })
}

// 搜索返回将SearchInts应用于接收方的结果，x。
func (p IntSlice) Search(x int) int { return SearchInts(p, x) }

// 搜索返回将SearchFloat64s应用于接收方的结果，x。
func (p Float64Slice) Search(x float64) int { return SearchFloat64s(p, x) }

// 搜索返回将SearchString应用于接收方的结果接收器和x.
func (p StringSlice) Search(x string) int { return SearchStrings(p, x) }
